这怕是NOIp2015中最毒瘤的几道题之一了吧
作为一个蒟蒻，鄙人表示这个题非常的难，于是就写一篇题解庆祝一下。
首先看到这道题，嗯，一棵树。然后呢？似乎有很多链，那就要涉及到LCA了，由于树剖常数较小，而且比较好写，所以果断选择树剖。
再看几眼，我们发现这要求某个最小值，仔细分析也能明白答案是符合单调性的，那么果断二分。但是check函数是个问题，我们可以把所有大于mid的链都找出来，然后再判断是否有一条边同时经过这些链并且删去后可以使最大边小于mid。那么后面这个判断我们用树上差分来完成。
那么AC代码呼之欲出。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
using namespace std;
int n,m,cnt,ans,num,mx_edge,mx_plan;
int head[N],siz[N],son[N],fa[N],dep[N],top[N],dis[N],sum[N],pre[N];
bool flag;
struct edge
{
int to,nxt,weight;
};
struct plan
{
int st,ed,lca,dist;
};
edge e[N];
plan p[N];
il int read()
{
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
il void add_edge(int u,int v,int w)
{
e[++cnt]=(edge){v,head[u],w};
head[u]=cnt;
}
il void dfs1(int x)
{
siz[x]++;
for(ri i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa[x])
continue;
fa[v]=x;
dep[v]=dep[x]+1;
dis[v]=dis[x]+e[i].weight;
pre[v]=e[i].weight;
dfs1(v);
siz[x]+=siz[v];
if(siz[v]>siz[son[x]])
son[x]=v;
}
if(!siz[son[x]])
son[x]=x;
}
il void dfs2(int x,int bel)
{
top[x]=bel;
for(ri i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa[x])
continue;
if(v==son[x])
dfs2(v,bel);
else
dfs2(v,v);
}
}
il int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
return x;
}
il int DFS(int x,int tot,int mx)
{
for(ri i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa[x])
continue;
sum[x]+=DFS(v,tot,mx);
}
if(sum[x]>=tot&&pre[x]>=mx)
flag=1;
return sum[x];
}
il bool check(int limit)
{
memset(sum,0,sizeof(sum));
flag=0,num=0;
for(ri i=1;i<=m;i++)
if(p[i].dist>limit)
{
sum[p[i].st]++,sum[p[i].ed]++,sum[p[i].lca]-=2;
num++;
}
if(num==0)
return 1;
int x=DFS(1,num,mx_plan-limit);
return flag;
}
int main()
{
n=read(),m=read();
for(ri i=1;i<=n-1;i++)
{
int u=read(),v=read(),w=read();
add_edge(u,v,w);
add_edge(v,u,w);
mx_edge=max(mx_edge,w);
}
dfs1(1);
dfs2(1,1);
for(ri i=1;i<=m;i++)
{
p[i].st=read(),p[i].ed=read();
p[i].lca=LCA(p[i].st,p[i].ed);
p[i].dist=dis[p[i].st]+dis[p[i].ed]-dis[p[i].lca]*2;
mx_plan=max(mx_plan,p[i].dist);
}
int L=mx_plan-mx_edge,R=mx_plan;
while(L<=R)
{
int mid=(L+R)>>1;
if(check(mid))
ans=mid,R=mid-1;
else
L=mid+1;
}
printf("%d",ans);
return 0;
}
然后我们会发现，这个东西效率极其之低，跑的慢的要死。那么就没办法了吗？显然不是。我们要知道树是有dfs序的，把dfs序弄出来不就可以在序列上搞了吗？省去了递归之后复杂度自然更优秀。
以下是几段核心代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20inline void dfs(int x)
{
siz[x]++,dfn[++dfn[0]]=x;
for(ri i=head[x];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa[x])
continue;
fa[v]=x;
dep[v]=dep[x]+1;
dis[v]=dis[x]+e[i].weight;
pre[v]=e[i].weight;
dfs1(v);
siz[x]+=siz[v];
if(siz[v]>siz[son[x]])
son[x]=v;
}
if(!siz[son[x]])
son[x]=x;
}
这是树剖经典dfs，不过是加了dfs序和差分的元素罢了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18inline bool check(int limit)
{
memset(sum,0,sizeof(sum));
num=0;
for(ri i=1;i<=m;i++)
if(p[i].dist>limit)
{
sum[p[i].st]++,sum[p[i].ed]++,sum[p[i].lca]-=2;
num++;
}
for(ri i=n;i;i--)
{
sum[fa[dfn[i]]]+=sum[dfn[i]];
if(pre[dfn[i]]>=mx_plan-limit&&sum[dfn[i]]>=num)
return 1;
}
return 0;
}
以上是很妙的一段修改，省去了差分中的递归过程，改用简洁的一层循环1
2for(ri i=1;i<=dfn[0];i++)
top[dfn[i]]=son[fa[dfn[i]]]==dfn[i]?top[fa[dfn[i]]]:dfn[i];
以上是另一处很妙的修改，这是树剖中确定每个点所属重链的过程，因为dfs序的存在也由递归被简化为一层循环.
这样就快很多了，大概速度是原来的4倍。
但还是不满意啊，那就改读入优化吧1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17struct io
{
char op[10000000],*s;
io()
{
fread(s=op,1,1<<26,stdin);
}
il int read()
{
int u = 0;
while(*s<48)
s++;
while(*s>32)
u=u*10+*s++-48;
return u;
}
};
用上了传说中最快的读入优化后，速度终于快起来了！
最后是跑出了392ms（O2）的好成绩，大概能进第二面。
于是就切掉了一道紫题DA☆ZE